package lc20240621;

import java.util.Arrays;

public class Median {
    public static void main(String[] args) {
        int[] nums1={1,3};
        int[] nums2={2,4};
        double v = find(nums1, nums2);
        System.out.println(v);
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i=0;
        int j=0;
        int l1=nums1.length;
        int l2=nums2.length;
        int[] res=new int[l1+l2];
        int k=0;
        while (i<l1&&j<l2){
            if (nums1[i]<nums2[j]){
                res[k]=nums1[i];
                i++;
            }else {
                res[k]=nums2[j];
                j++;
            }
            k++;
        }
        if (i!=l1){
            while (i<l1){
                res[k]=nums1[i];
                k++;
                i++;
            }
        }
        if (j!=l2){
            while (j<l2){
                res[k]=nums2[j];
                j++;
                k++;
            }
        }
        int length = res.length;

        if (length%2==0){
            int a=length/2;
            return (double) (res[a] + res[a - 1]) /2;
        }else {
            int a=length/2;
            return res[a];
        }
    }

    public static double find(int[] nums1,int[] nums2){
        // 确保 nums1 是较短的那个数组
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;

        while (iMin <= iMax) {
            //初始值
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i<m&&nums1[i]<nums2[j-1]){
                iMin=i+1;//数组一的分割点太小，需要往右移动
            }else if (i>0&&nums1[i-1]>nums2[j]){
                iMax=i-1;//数组1的分割点太大了。需要往左移动
            }else {
                //找到合适的分割点，意味着两个数组左半部分都小于nums1[i],无论右半部分怎样排列，现在i，j已经是中位数的两个索引
                int maxOfLeft;
                if (i==0){
                    maxOfLeft=nums2[j-1];
                } else if (j==0) {
                    maxOfLeft=nums1[i-1];
                }else {
                    maxOfLeft=Math.max(nums1[i-1],nums2[j-1]);
                }

                if ((m+n)%2==1){
                    return maxOfLeft;
                }

                int maxOfRight;
                if (i==m){
                    maxOfRight=nums2[j];
                }else if (j==n){
                    maxOfRight=nums1[j];
                }else{
                    maxOfRight=Math.min(nums1[i],nums2[j]);
                }

                return (maxOfLeft+maxOfRight)/2.0;
            }
        }

        throw new IllegalArgumentException("Input arrays are not valid.");
    }
}
